package leetcode.editor.cn;

//给定一个经过编码的字符串，返回它解码后的字符串。
//
// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//
// 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//
// 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
//
//
//
// 示例 1：
//
//
//输入：s = "3[a]2[bc]"
//输出："aaabcbc"
//
//
// 示例 2：
//
//
//输入：s = "3[a2[c]]"
//输出："accaccacc"
//
//
// 示例 3：
//
//
//输入：s = "2[abc]3[cd]ef"
//输出："abcabccdcdcdef"
//
//
// 示例 4：
//
//
//输入：s = "abc3[cd]xyz"
//输出："abccdcdcdxyz"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 30
//
// s 由小写英文字母、数字和方括号
// '[]' 组成
// s 保证是一个 有效 的输入。
// s 中所有整数的取值范围为
// [1, 300]
//
//
// Related Topics 栈 递归 字符串 👍 1916 👎 0

import java.util.*;

//Java：字符串解码
public class DecodeString {
    public static void main(String[] args) {
        Solution solution = new DecodeString().new Solution();
        String s = solution.decodeString("3[a]2[bc]");
        System.out.println(s);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int ptr;

        public String decodeString(String s) {
            Stack<String> stk = new Stack<String>();
            ptr = 0;
            while (ptr < s.length()) {
                char cur = s.charAt(ptr);
                if (Character.isDigit(cur)) {
                    // 获取一个数字并进栈
                    String digits = getDigits(s);
                    stk.push(digits);
                } else if (Character.isLetter(cur) || cur == '[') {
                    // 获取一个字母并进栈
                    stk.push(String.valueOf(s.charAt(ptr++)));
                } else {//走到这个分支的一定是 ]
                    ++ptr;//  跳过 ]

                    StringBuffer  sub = new StringBuffer ();
                    while (!"[".equals(stk.peek())) {
                        sub.insert(0,stk.pop());//注意顺序
                    }
                    // 左括号出栈
                    stk.pop();//    此时 [  出栈
                    // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                    int repTime = Integer.parseInt(stk.pop());
                    StringBuffer t = new StringBuffer();
                    String o = sub.toString();//获取要重复的字符串
                    // 构造字符串
                    while (repTime-- > 0) {
                        t.append(o);
                    }
                    // 将构造好的字符串入栈
                    stk.push(t.toString());
                }
            }

            return getStackString(stk);
        }

        /**
         * 把栈里面元素化成字符串，从栈底开始
         * @param stack
         * @return
         */
        public String getStackString(Stack<String> stack) {
            StringBuilder stringBuilder = new StringBuilder();
            // 使用栈的迭代器按原始顺序遍历（从栈底到栈顶）
            for (String item : stack) {
                stringBuilder.append(item);
            }
            return stringBuilder.toString();
        }


        /**
         * 获取一个数字，注意可能存在多个数字
         * @param s
         * @return
         */
        public String getDigits(String s) {
            StringBuffer ret = new StringBuffer();
            while (Character.isDigit(s.charAt(ptr))) {
                ret.append(s.charAt(ptr++));
            }
            return ret.toString();
        }

    }




//leetcode submit region end(Prohibit modification and deletion)

}
